package pro.softzhang.algo.lc600;

import pro.softzhang.algo.common.TrieNode;

public class LC676_ImplementMagicDictionary {
    public static void main(String[] args) {

    }

    static class MagicDictionary {

        private TrieNode root;

        public MagicDictionary() {
            root = new TrieNode();
        }

        public void buildDict(String[] dictionary) {
            for (String word : dictionary) {
                TrieNode node = root;
                for (char ch : word.toCharArray()) {
                    int idx = ch - 'a';
                    if(node.children[idx] == null) {
                        node.children[idx] = new TrieNode();
                    }
                    node = node.children[idx];
                }
                node.isWord = true;
            }
        }

        public boolean search(String searchWord) {
            return doSearch(root, searchWord, 0, 0);
        }

        private boolean doSearch(TrieNode root, String word, int i, int edit) {
            if(root == null) {
                return false;
            }

            if(root.isWord && i == word.length() && edit == 1) {
                return true;
            }

            if(i < word.length() && edit <= 1) {
                boolean found = false;
                for (int j = 0; j < 26 && !found; j++) {
                    int next = j == word.charAt(i) - 'a' ? edit : edit + 1;
                    found = doSearch(root.children[j], word, i + 1, next);
                }
                return found;
            }
            return false;
        }
    }
}